# -*-coding = utf-8 -*-

# @Time: 2021/4/23 16:42
# @Author: bistro
# @File: p368.py
# @Software: PyCharm
# 368.最大整除子集
from typing import List


class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if n == 1:
            return nums
        nums.sort()
        dp = [0]*n
        f = [0]*n
        for i in range(0, n):
            length, prev = 1, i
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[j] + 1 > length:
                        length = dp[j] + 1
                        prev = j
            dp[i] = length
            f[i] = prev
        # 找最大值
        maxl = -1
        idx = -1
        for i in range(n):
            if maxl < dp[i]:
                maxl = dp[i]
                idx = i
        # 找最长序列 回溯
        res = []
        while maxl > 0:
            res.append(nums[idx])
            idx = f[idx]
            maxl -= 1
        res.sort()
        return res


s = Solution()
print(s.largestDivisibleSubset([4, 8, 10, 240]))
